File: cmu-user.info Node: Precise Type Checking-Footnotes, Up: Precise Type Checking
(3) There are a few circumstances where a type declaration is discarded
rather than being used as type assertion. This doesn't affect safety
much, since such discarded declarations are also not believed to be true
by the compiler.
(4) The initial value need not be of this type as long as the
corresponding argument to the constructor is always supplied, but this
will cause a compile-time type warning unless `required-argument'
is used.
File: cmu-user.info Node: Weakened Type Checking, Prev: Precise Type Checking, Up: Types in Python
Weakened Type Checking
----------------------
When the value for the `speed' optimization quality is greater than
`safety', and `safety' is not `0', then type checking is weakened to
reduce the speed and space penalty. In structure-intensive code this
can double the speed, yet still catch most type errors. Weakened type
checks provide a level of safety similar to that of "safe" code in other
Common Lisp compilers.
A type check is weakened by changing the check to be for some
convenient supertype of the asserted type. For example,
`(integer 3 17)' is changed to `fixnum',
`(simple-vector 17)' to `simple-vector', and structure
types are changed to `structure'. A complex check like:
(or node hunk (member :foo :bar :baz))
will be omitted entirely (i.e., the check is weakened to `*'.) If a
precise check can be done for no extra cost, then no weakening is done.
Although weakened type checking is similar to type checking done by
other compilers, it is sometimes safer and sometimes less safe.
Weakened checks are done in the same places is precise checks, so all
the preceding discussion about where checking is done still applies.
Weakened checking is sometimes somewhat unsafe because although the
check is weakened, the precise type is still input into type inference.
In some contexts this will result in type inferences not justified by
the weakened check, and hence deletion of some type checks that would be
done by conventional compilers.
For example, if this code was compiled with weakened checks:
(defstruct foo
(a nil :type simple-string))
(defstruct bar
(a nil :type single-float))
(defun myfun (x)
(declare (type bar x))
(* (bar-a x) 3.0))
and `myfun' was passed a `foo', then no type error would be signalled,
and we would try to multiply a `simple-vector' as though it were a float
(with unpredictable results.) This is because the check for `bar' was
weakened to `structure', yet when compiling the call to `bar-a', the
compiler thinks it knows it has a `bar'.
Note that normally even weakened type checks report the precise type in error
messages. For example, if `myfun''s `bar' check is weakened to
`structure', and the argument is false, then the error will be:
Type-error in MYFUN:
NIL is not of type BAR
However, there is some speed and space cost for signalling a precise error, so
the weakened type is reported if the `speed' optimization quality is `3' or
`debug' quality is less than `1':
Type-error in MYFUN:
NIL is not of type STRUCTURE
? for further discussion of the `optimize' declaration.
File: cmu-user.info Node: Getting Existing Programs to Run, Prev: Types in Python, Up: The Compiler, Next: Compiler Policy
Getting Existing Programs to Run
================================
Since Python does much more comprehensive type checking than other Lisp
compilers, Python will detect type errors in many programs that have been
debugged using other compilers. These errors are mostly incorrect
declarations, although compile-time type errors can find actual bugs if parts
of the program have never been tested.
Some incorrect declarations can only be detected by run-time type
checking. It is very important to initially compile programs with full
type checks and then test this version. After the checking version has
been tested, then you can consider weakening or eliminating type checks.
This applies even to previously debugged programs. Python does much
more type inference than other Common Lisp compilers, so believing an
incorrect declaration does much more damage.
The most common problem is with variables whose initial value doesn't match the
type declaration. Incorrect initial values will always be flagged by a
compile-time type error, and they are simple to fix once located. Consider
this code fragment:
(prog (foo)
(declare (fixnum foo))
(setq foo ...)
...)
Here the variable `foo' is given an initial value of false, but is declared
to be a `fixnum'. Even if it is never read, the initial value of a variable
must match the declared type. There are two ways to fix this problem. Change
the declaration:
(prog (foo)
(declare (type (or fixnum null) foo))
(setq foo ...)
...)
or change the initial value:
(prog ((foo 0))
(declare (fixnum foo))
(setq foo ...)
...)
It is generally preferable to change to a legal initial value rather
than to weaken the declaration, but sometimes it is simpler to weaken
the declaration than to try to make an initial value of the appropriate
type.
Another declaration problem occasionally encountered is incorrect declarations
on `defmacro' arguments. This probably usually happens when a function is
converted into a macro. Consider this macro:
(defmacro my-1+ (x)
(declare (fixnum x))
`(the fixnum (1+ ,x)))
Although legal and well-defined CMU Common Lisp, this meaning of this definition is
almost certainly not what the writer intended. For example, this call is
illegal:
(my-1+ (+ 4 5))
The call is illegal because the argument to the macro is `(+ 4 5)', which
is a `list', not a `fixnum'. Because of macro semantics, it is hardly ever
useful to declare the types of macro arguments. If you really want to assert
something about the type of the result of evaluating a macro argument, then put
a `the' in the expansion:
(defmacro my-1+ (x)
`(the fixnum (1+ (the fixnum ,x))))
In this case, it would be stylistically preferable to change this macro
back to a function and declare it inline. Macros have no efficiency
advantage over inline functions when using Python. ?.
Some more subtle problems are caused by incorrect declarations that can't be
detected at compile time. Consider this code:
(do ((pos 0 (position #\a string :start (1+ pos))))
((null pos))
(declare (fixnum pos))
...)
Although `pos' is almost always a `fixnum', it is false at the end of
the loop. If this example is compiled with full type checks (the
default), then running it will signal a type error at the end of the
loop. If compiled without type checks, the program will go into an
infinite loop (or perhaps `position' will complain because `(1+ nil)'
isn't a sensible start.) Why? Because if you compile without type
checks, the compiler just quietly believes the type declaration. Since
`pos' is always a `fixnum', it is never nil, so `(null pos)' is never
true, and the loop exit test is optimized away. Such errors are
sometimes flagged by unreachable code notes (?), but it is still
important to initially compile any system with full type checks, even if
the system works fine when compiled using other compilers.
In this case, the fix is to weaken the type declaration to `(or fixnum
null)'. (5) (*Note Getting Existing Programs to Run-Footnotes::) Note
that there is usually little performance penalty for weakening a
declaration in this way. Any numeric operations in the body can still
assume the variable is a `fixnum', since
false is not a legal numeric argument. Another possible fix would be to say:
(do ((pos 0 (position #\a string :start (1+ pos))))
((null pos))
(let ((pos pos))
(declare (fixnum pos))
...))
This would be preferable in some circumstances, since it would allow a
non-standard representation to be used for the local `pos' variable in the
loop body (see section ?.)
In summary, remember that ALL values that a variable EVER has must be of
the declared type, and that you should test using safe code initially.
File: cmu-user.info Node: Getting Existing Programs to Run-Footnotes, Up: Getting Existing Programs to Run
(5) Actually, this declaration is totally unnecessary in Python, since
it already knows `position' returns a non-negative `fixnum' or
false.
File: cmu-user.info Node: Compiler Policy, Prev: Getting Existing Programs to Run, Up: The Compiler, Next: Open Coding and Inline Expansion
Compiler Policy
===============
The policy is what tells the compiler HOW to compile a program. This is
logically (and often textually) distinct from the program itself. Broad
control of policy is provided by the `optimize' declaration; other
declarations and variables control more specific aspects of compilation.
* Menu:
* The Optimize Declaration::
* The Optimize-Interface Declaration::
File: cmu-user.info Node: The Optimize Declaration, Prev: Compiler Policy, Up: Compiler Policy, Next: The Optimize-Interface Declaration
The Optimize Declaration
------------------------
The `optimize' declaration recognizes six different QUALITIES. The
qualities are conceptually independent aspects of program performance.
In reality, increasing one quality tends to have adverse effects on
other qualities. The compiler compares the relative values of qualities
when it needs to make a trade-off; i.e., if `speed' is greater than
`safety', then improve speed at the cost of safety.
The default for all qualities (except `debug') is `1'. Whenever
qualities are equal, ties are broken according to a broad idea of what a
good default environment is supposed to be. Generally this downplays
`speed', `compile-speed' and `space' in favor of `safety' and `debug'.
Novice and casual users should stick to the default policy. Advanced
users often want to improve speed and memory usage at the cost of safety
and debuggability.
If the value for a quality is `0' or `3', then it may have a special
interpretation. A value of `0' means "totally unimportant", and a `3'
means "ultimately important." These extreme optimization values enable
"heroic" compilation strategies that are not always desirable and
sometimes self-defeating. Specifying more than one quality as `3' is
not desirable, since it doesn't tell the compiler which quality is most
important.
These are the optimization qualities:
`speed'
How fast the program should is run. `speed 3' enables some
optimizations that hurt debuggability.
`compilation-speed'
How fast the compiler should run. Note that increasing this above
`safety' weakens type checking.
`space'
How much space the compiled code should take up. Inline expansion
is mostly inhibited when `space' is greater than `speed'. A value
of `0' enables promiscuous inline expansion. Wide use of a `0'
value is not recommended, as it may waste so much space that run
time is slowed. ? for a discussion of inline expansion.
`debug'
How debuggable the program should be. The quality is treated
differently from the other qualities: each value indicates a
particular level of debugger information; it is not compared with
the other qualities. *Note Compiler Policy Control:: for more
details.
`safety'
How much error checking should be done. If `speed', `space' or
`compilation-speed' is more important than `safety', then type
checking is weakened (*Note Weakened Type Checking::). If `safety'
if `0', then no run time error checking is done. In addition to
suppressing type checks, `0' also suppresses argument count
checking, unbound-symbol checking and array bounds checks.
`extensions:inhibit-warnings'
This is a CMU extension that determines how little (or how much)
diagnostic output should be printed during compilation. This
quality is compared to other qualities to determine whether to
print style notes and warnings concerning those qualities. If
`speed' is greater than `inhibit-warnings', then notes about how to
improve speed will be printed, etc. The default value is `1', so
raising the value for any standard quality above its default
enables notes for that quality. If `inhibit-warnings' is `3', then
all notes and most non-serious warnings are inhibited. This is
useful with `declare' to suppress warnings about unavoidable
problems.
File: cmu-user.info Node: The Optimize-Interface Declaration, Prev: The Optimize Declaration, Up: Compiler Policy
The Optimize-Interface Declaration
----------------------------------
The `extensions:optimize-interface' declaration is identical in syntax
to the `optimize' declaration, but it specifies the policy used during
compilation of code the compiler automatically generates to check the
number and type of arguments supplied to a function. It is useful to
specify this policy separately, since even thoroughly debugged functions
are vulnerable to being passed the wrong arguments. The
`optimize-interface' declaration can specify that arguments should be
checked even when the general `optimize' policy is unsafe.
Note that this argument checking is the checking of user-supplied
arguments to any functions defined within the scope of the declaration,
`not' the checking of arguments to Common Lisp primitives that appear in
those definitions.
The idea behind this declaration is that it allows the definition of
functions that appear fully safe to other callers, but that do no
internal error checking. Of course, it is possible that arguments may
be invalid in ways other than having incorrect type. Functions compiled
unsafely must still protect themselves against things like user-supplied
array indices that are out of bounds and improper lists. See also the
:context-declarations option to with-compilation-unit *Note Compilation
Units::.
File: cmu-user.info Node: Open Coding and Inline Expansion, Prev: Compiler Policy, Up: The Compiler
Open Coding and Inline Expansion
================================
Since CMU Common Lisp forbids the redefinition of standard functions (6)
(*Note Open Coding and Inline Expansion-Footnotes::), the compiler can
have special knowledge of these standard functions embedded in it. This
special knowledge is used in various ways (open coding, inline
expansion, source transformation), but the implications to the user are
basically the same:
* Attempts to redefine standard functions may be frustrated, since
the function may never be called. Although it is technically
illegal to redefine standard functions, users sometimes want to
implicitly redefine these functions when they are debugging using
the `trace' macro. Special-casing of standard functions can be
inhibited using the `notinline' declaration.
* The compiler can have multiple alternate implementations of
standard functions that implement different trade-offs of speed,
space and safety. This selection is based on the compiler policy,
*Note Compiler Policy::.
When a function call is open coded, inline code whose effect is
equivalent to the function call is substituted for that function call.
When a function call is closed coded, it is usually left as is,
although it might be turned into a call to a different function with
different arguments. As an example, if `nthcdr' were to be open
coded, then
(nthcdr 4 foobar)
might turn into
(cdr (cdr (cdr (cdr foobar))))
or even
(do ((i 0 (1+ i))
(list foobar (cdr foobar)))
((= i 4) list))
If `nth' is closed coded, then
(nth x l)
might stay the same, or turn into something like:
(car (nthcdr x l))
In general, open coding sacrifices space for speed, but some functions
(such as `car') are so simple that they are always open-coded. Even
when not open-coded, a call to a standard function may be transformed
into a different function call (as in the last example) or compiled as
static call. Static function call uses a more efficient calling
convention that forbids redefinition.
File: cmu-user.info Node: Open Coding and Inline Expansion-Footnotes, Up: Open Coding and Inline Expansion
(6) See the proposed X3J13 "lisp-symbol-redefinition" cleanup.
File: cmu-user.info Node: Advanced Compiler Use and Efficiency Hints, Prev: The Compiler, Up: Top, Next: UNIX Interface
Advanced Compiler Use and Efficiency Hints
******************************************
By Robert MacLachlan
* Menu:
* Advanced Compiler Introduction::
* More About Types in Python::
* Type Inference::
* Source Optimization::
* Tail Recursion::
* Local Call::
* Block Compilation::
* Inline Expansion::
* Object Representation::
* Numbers::
* General Efficiency Hints::
* Efficiency Notes::
* Profiling::
File: cmu-user.info Node: Advanced Compiler Introduction, Prev: Advanced Compiler Use and Efficiency Hints, Up: Advanced Compiler Use and Efficiency Hints, Next: More About Types in Python
Advanced Compiler Introduction
==============================
In CMU Common Lisp, as is any language on any computer, the path to
efficient code starts with good algorithms and sensible programming
techniques, but to avoid inefficiency pitfalls, you need to know some of
this implementation's quirks and features. This chapter is mostly a
fairly long and detailed overview of what optimizations Python does.
Although there are the usual negative suggestions of inefficient
features to avoid, the main emphasis is on describing the things that
programmers can count on being efficient.
The optimizations described here can have the effect of speeding up
existing programs written in conventional styles, but the potential for
new programming styles that are clearer and less error-prone is at least
as significant. For this reason, several sections end with a discussion
of the implications of these optimizations for programming style.
Writing efficient code that works is a complex and prolonged process. It is
important not to get so involved in the pursuit of efficiency that you lose
sight of what the original problem demands. Remember that:
* The program should be correct -- it doesn't matter how quickly you
get the wrong answer.
* Both the programmer and the user will make errors, so the program
must be robust -- it must detect errors in a way that allows easy
correction.
* A small portion of the program will consume most of the resources,
with the bulk of the code being virtually irrelevant to efficiency
considerations. Even experienced programmers familiar with the
problem area cannot reliably predict where these "hot spots" will
be.
The best way to get efficient code that is still worth using, is to separate
coding from tuning. During coding, you should:
* Use a coding style that aids correctness and robustness without
being incompatible with efficiency.
* Choose appropriate data structures that allow efficient algorithms
and object representations (?). Try to make interfaces abstract
enough so that you can change to a different representation if
profiling reveals a need.
* Whenever you make an assumption about a function argument or global
data structure, add consistency assertions, either with type
declarations or explicit uses of `assert', `ecase', etc.
During tuning, you should:
* Identify the hot spots in the program through profiling (section
?.)
* Identify inefficient constructs in the hot spot with efficiency
notes, more profiling, or manual inspection of the source. See
sections ? and ?.
* Add declarations and consider the application of optimizations.
See sections ?, ? and ?.
* If all else fails, consider algorithm or data structure changes.
If you did a good job coding, changes will be easy to introduce.
File: cmu-user.info Node: More About Types in Python, Prev: Advanced Compiler Introduction, Up: Advanced Compiler Use and Efficiency Hints, Next: Type Inference
More About Types in Python
==========================
This section goes into more detail describing what types and declarations are
recognized by Python. The area where Python differs most radically from
previous Common Lisp compilers is in its support for types:
* Precise type checking helps to find bugs at run time.
* Compile-time type checking helps to find bugs at compile time.
* Type inference minimizes the need for generic operations, and also
increases the efficiency of run time type checking and the
effectiveness of compile time type checking.
* Support for detailed types provides a wealth of opportunity for
operation-specific type inference and optimization.
* Menu:
* More Types Meaningful::
* Canonicalization::
* Member Types::
* Union Types::
* The Empty Type::
* Function Types::
* The Values Declaration::
* Structure Types::
* The Freeze-Type Declaration::
* Type Restrictions::
* Type Style Recommendations::
File: cmu-user.info Node: More Types Meaningful, Prev: More About Types in Python, Up: More About Types in Python, Next: Canonicalization
More Types Meaningful
---------------------
CMU Common Lisp has a very powerful type system, but conventional Common
Lisp implementations typically only recognize the small set of types
special in that implementation. In these systems, there is an
unfortunate paradox: a declaration for a relatively general type like
`fixnum' will be recognized by the compiler, but a highly specific
declaration such as `(integer 3 17)' is totally ignored.
This is obviously a problem, since the user has to know how to specify
the type of an object in the way the compiler wants it. A very minimal
(but rarely satisfied) criterion for type system support is that it be
no worse to make a specific declaration than to make a general one.
Python goes beyond this by exploiting a number of advantages obtained
from detailed type information.
Using more restrictive types in declarations allows the compiler to do
better type inference and more compile-time type checking. Also, when
type declarations are considered to be consistency assertions that
should be verified (conditional on policy), then complex types are
useful for making more detailed assertions.
Python "understands" the list-style `or', `member', `function', array and
number type specifiers. Understanding means that:
* If the type contains more information than is used in a particular
context, then the extra information is simply ignored, rather than
derailing type inference.
* In many contexts, the extra information from these type specifier
is used to good effect. In particular, type checking in `Python'
is PRECISE, so these complex types can be used in declarations to
make interesting assertions about functions and data structures
(*Note Precise Type Checking::.) More specific declarations also
aid type inference and reduce the cost for type checking.
For related information, ? for numeric types, and section ? for array
types.
File: cmu-user.info Node: Canonicalization, Prev: More Types Meaningful, Up: More About Types in Python, Next: Member Types
Canonicalization
----------------
When given a type specifier, Python will often rewrite it into a different
(but equivalent) type. This is the mechanism that Python uses for detecting
type equivalence. For example, in Python's canonical representation, these
types are equivalent:
(or list (member :end)) == (or cons (member nil :end))
This has two implications for the user:
* The standard symbol type specifiers for `atom', `null', `fixnum',
etc., are in no way magical. The null type is actually defined to
be `(member nil)', list is `(or cons null)', and fixnum is
`(signed-byte 30)'.
* When the compiler prints out a type, it may not look like the type
specifier that originally appeared in the program. This is
generally not a problem, but it must be taken into consideration
when reading compiler error messages.
File: cmu-user.info Node: Member Types, Prev: Canonicalization, Up: More About Types in Python, Next: Union Types
Member Types
------------
The member type specifier can be used to represent
"symbolic" values, analogous to the enumerated types of Pascal. For
example, the second value of `find-symbol' has this type:
(member :internal :external :inherited nil)
Member types are very useful for expressing consistency constraints on data
